Información del Plan Docente

1. Información Básica

1.1. Objetivos de la asignatura

Se trata de una asignatura de formación básica dentro del grado de Matemáticas, y uno de los principales objetivos es que los conocimientos teóricos y las técnicas adquiridas sirvan como base para asignaturas de cursos posteriores.

Por otra parte, en la modelización, formulación, análisis y resolución de muchos problemas científicos, se requiere conocer los métodos de teoría de grafos y se necesitan las herramientas de análisis combinatorio. Por ello, otro de los objetivos de la asignatura es saber reconocer este tipo de problemas y saber aplicar las técnicas adecuadas para su resolución.

Finalmente, la asignatura tiene un gran valor formativo, ya que sirve para desarrollar la capacidad analítica, la capacidad de abstracción y el pensamiento lógico.

Estos planteamientos y objetivos están alineados con los siguientes Objetivos de Desarrollo Sostenible (ODS) de la Agenda 2030 de Naciones Unidas (https://www.un.org/sustainabledevelopment/es/), de tal manera que la adquisición de los resultados de aprendizaje de la asignatura proporciona capacitación y competencia para contribuir en cierta medida a su logro: Objetivo 4: Educación de calidad; Objetivo 5: Igualdad de género; Objetivo 8: Trabajo decente y crecimiento económico; Objetivo 9: Industria, innovación e infraestructuras; Objetivo 10: Reducción de las desigualdades; Objetivo 17: Alianzas para lograr los objetivos.

1.2. Contexto y sentido de la asignatura en la titulación

Se trata de una asignatura del módulo Matemática Discreta y Optimización dedicada esencialmente al estudio de estructuras discretas y a problemas de enumeración. Para su correcto desarrollo se requieren conocimientos básicos de álgebra lineal y análisis matemático.

En muchas materias del ámbito de las matemáticas los problemas subyacentes son de tipo combinatorio, por ello una base sólida en combinatoria es esencial en casi todas las ramas clásicas de las matemáticas, como probabilidad, geometría, álgebra…

Por otra parte, las estructuras discretas de grafos y árboles aparecen de forma natural en las materias de Informática. Señalar por último, que también dentro del campo de la Informática, para el análisis de la complejidad computacional de algoritmos se necesita conocer y manejar los métodos de enumeración.

1.3. Recomendaciones para cursar la asignatura

El estudio y trabajo continuado son esenciales para superar la asignatura. Se recomienda en particular la realización de los ejercicios propuestos. Una de las dificultades de la asignatura, sobre todo en los temas de combinatoria, radica en la dificultad de distinguir los conjuntos sobre los que se trabaja, de precisar que elementos los forman. La consulta de dudas al profesor y la clarificación de conceptos son fundamentales para progresar en la materia.

2. Competencias y resultados de aprendizaje

2.1. Competencias

Al superar la asignatura, el estudiante será más competente para:

• Desenvolverse en el manejo de los objetivos descritos (Ver apartado Resultados de aprendizaje).
• Resolver problemas matemáticos mediante habilidades de cálculo combinatorio y técnicas de teoría de grafos.
• Proponer, analizar, validar e interpretar modelos de situaciones reales sencillas, utilizando las herramientas matemáticas adecuadas a los fines que se persigan.
• Comprender y utilizar el lenguaje y método matemáticos.
• Conocer demostraciones rigurosas de los teoremas básicos de combinatoria y teoría de grafos.
• Aprender nuevos conocimientos y técnicas matemáticas de forma autónoma.
• Haber desarrollado habilidades de aprendizaje necesarias para emprender estudios posteriores en matemáticas con un alto grado de autonomía.

2.2. Resultados de aprendizaje

El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados:

• Es capaz de resolver problemas elementales de ordenación y enumeración.
• Conoce y maneja el concepto de función generatriz y el de fórmula de recurrencia.
• Es capaz de utilizar las funciones generatrices para obtener fórmulas para problemas de enumeración.
• Conoce el lenguaje y las aplicaciones más elementales de la teoría de grafos.
• Es capaz de aplicar los algoritmos básicos de teoría de grafos para resolver problemas.

2.3. Importancia de los resultados de aprendizaje

Proporcionan una formación de carácter básico dentro del grado (ver Contexto y sentido de la asignatura en la titulación).

Además, los problemas de tipo combinatorio, son probablemente los problemas matemáticos más frecuentes en situaciones cotidianas, como organización de turnos y horarios, distribuciones de personas en grupos, realización de sorteos, muestreo, etc. Ser capaz de resolver esos problemas básicos de combinatoria de forma clara y precisa es uno de los resultados del aprendizaje.

De la misma forma, los grafos o redes, son una de las estructuras matemáticas más frecuentes en situaciones reales, y conocer sus propiedades y los algoritmos básicos para resolución de problemas sobre ellos, es fundamental para la formación de un matemático.

3. Evaluación

3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba

El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluación:

Al terminar la primera parte de la asignatura (temas de combinatoria), se realizará una prueba parcial, donde se examinará al alumno sobre esos contenidos de combinatoria y se le calificará con una nota, P1, entre 0 y 10.

En la fecha oficial de una convocatoria se realizará un examen con dos partes diferenciadas, una con preguntas de combinatoria, la otra con cuestiones de teoría de grafos. Las calificaciones obtenidas en cada una de esas partes (E1 y E2) serán también sobre 10 puntos.

La calificación, C, de la asignatura, obtenida en esa convocatoria oficial será:

• Si P1 es menor que 4, C = 0.5*(E1+E2).
• Si P1 es mayor o igual que 4, C=0.5*(Max(P1,E1)+E2).

Habrán superado la asignatura en esa convocatoria quienes hayan obtenido una calificación C mayor o igual a 5.

4. Metodología, actividades de aprendizaje, programa y recursos

4.1. Presentación metodológica general

El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:

Clases de teoría. Consisten en lecciones impartidas por el profesor siguiendo principalmente el modelo de lección magistral, utilizando el apoyo de medios audiovisuales y recursos informáticos cuando sea conveniente, y procurando también cierta interacción con los estudiantes. Como máximo supondrán el 50% de las clases.

Técnicas y herramientas para la resolución de problemas. Se enseñarán técnicas de resolución de ejercicios y problemas en clase. Se propondrán también problemas y ejercicios, personales o en grupos reducidos. Estas actividades implican que los estudiantes tendrán que realizar por su parte un trabajo personal para la resolución de los problemas propuestos y la redacción de soluciones. Supondrán al menos el 40% de las clases.

Tutorías. Además de los horarios de tutorías personales establecidos por el profesor, los estudiantes dispondrán también de una dirección de correo electrónico para hacer consultas.

Trabajo personal. El estudio individual le permitirá asentar los conceptos explicados en las clases, así como aprender y aplicar adecuadamente las técnicas explicadas. También dedicará una parte importante de su tiempo a la resolución de los ejercicios propuestos.

La asignatura aparece en el Anillo Digital Docente (ADD) de la Universidad de Zaragoza. Así, el alumno puede obtener información sobre la asignatura, apuntes, material complementario, hojas de problemas, etc.

4.2. Actividades de aprendizaje

• Clases de teoría y problemas, realización de ejercicios y tutorías y sobre los siguientes tópicos: Combinatoria elemental, Funciones generatrices, Grafos, Camino óptimo y Problemas de flujo.
• Apoyo a la formación mediante documentos y enlaces  en la página de la asignatura en el ADD de la universidad, moodle.unizar.es (acceso restringido  a los alumnos matriculados).

Las actividades docentes y de evaluación se llevarán a cabo de modo presencial salvo que, debido a la situación sanitaria, las disposiciones emitidas por las autoridades competentes y por la Universidad de Zaragoza dispongan realizarlas de forma telemática o semitelemática con aforos reducidos rotatorios.

4.3. Programa

TEMA I

1. Combinatoria elemental: Permutaciones y combinaciones.
2. Coeficientes binomiales.
3. Recurrencias. Aplicaciones.
4. El principio de inclusión-exclusión. Aplicaciones.

TEMA II

5. Funciones generatrices.
6. Funciones generatrices racionales.

TEMA III

7. Definición y notaciones para grafos.
8. Problema de recorrido de un grafo. Algoritmos  BFS y DFS.
9. Aplicaciones. Cálculo de componentes y bases.
10. Número de árboles y caminos de un grafo.

TEMA IV

11. Grafos con costos. Algoritmos para calcular el árbol mínimo.
12. Caminos más cortos: Algoritmo de Dijkstra.
13. Técnicas PERT-CPM de planificación de proyectos.

TEMA V

14. Flujo en redes. Conceptos básicos.
15. Algoritmo de Ford- Fulkerson para cálculo de máximo flujo.
16. Teoremas de conectividad de Menger.
17. Matching en grafos bipartitos.
18. Algunos problemas NP-duros sobre grafos. 

4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave

Calendario de sesiones presenciales:

• Las clases magistrales y de problemas (hasta 4 horas a la semana) se imparten según horario establecido por el centro, publicado con anterioridad a la fecha de comienzo del curso.
• Realización de un examen parcial escrito al finalizar la primera parte de la asignatura (Combinatoria), y de un examen final escrito, en las fechas y convocatorias determinadas por el centro.
• Desde el primer día de clase los alumnos dispondrán de un calendario detallado de fechas de exámenes.

4.5. Bibliografía y recursos recomendados

La bibliografía recomendada es la siguiente:

• Básica: Apuntes de la asignatura. Disponibles online en la página de la asignatura en el ADD.
• Complementaria: http://psfunizar10.unizar.es/br13/egAsignaturas.php?codigo=27005